Real-world problems (such as movement of impurities in silicon semiconductor components) sometimes can be modeled and simulated on computers. Many simulators provide output as mixed-element meshes, i.e., meshes including tetrahedral and non-tetrahedral elements. Tetrahedra are three-dimensional shapes with four vertices and four triangular faces. Examples of non-tetrahedral shapes are blocks, pyramids and prisms.
It has been desired to further process the simulator output, such as to run it through visualization or testing software programs. However, some such software programs require input to be tetrahedral meshes, and cannot accommodate non-tetrahedral meshes. Thus, techniques were sought and developed for tetrahdedralizing mixed-element meshes. A particular challenge has been to tetrahedralize a “non-conformal” mixed-element mesh, i.e., one in which triangular element faces can abut quadrilateral element faces in the mesh. Three dimensional tetrahedralization is a well known problem. See, e.g., G. Albertelli, R. Crawfis, “Efficient subdivision of finite-element datasets into consistent tetrahedra,” IEEE (1997); J. Dompierre, P. Labbe, M. Vallet, R. Camarero, “How to subdivide pyramids, prisms and hexahedra into tetrahedra,” Centre de recherche en calcul applique (CERCA), presented at the 8th International Meshing Roundtable, South Lake Tahoe, Calif. (October 1999), pages 195–204.
To subdivide non-tetrahedra (e.g., prisms and hexahedra) into tetrahedra reduces to selecting how to split each quadrilateral face with a diagonal. For example, prisms have three quadrilateral faces; each quadrilateral face can be split by a diagonal in two different ways; therefore there are eight possible face-splitting combinations for each prism. Only six of these can be subdivided into three tetrahedra without Steiner points; the other two require Steiner points, and produce eight tetrahedra. Similarly, hexahedra have six quadrilateral faces, resulting in 26=64 possible face-splitting combinations. Only 46 of these can be subdivided into five or six tetrahedra without Steiner points; the other 18 are indivisible.
When a non-tetrahedral shape is indivisible, to subdivide it requires creation of a “Steiner point”. Additional Steiner points increase the number of nodes and elements in the mesh. Steiner points in the input meshes interfere with the speed and the convergence behavior of software processing the meshes. Conventional approaches to subdividing non-conformal mixed-element meshes into tetrahedral meshes have needed to add relatively many undesirable “Steiner points” to generate the tetrahedral mesh. A Steiner point is a node added to the element interior, usually at its center.
In an initially conformal mesh, there are no initial constraints on how these quadrilateral faces must be split, except that abutting quadrilateral faces must be split in a consistent manner (i.e., the diagonal selected for the face from one element must match the diagonal selected for the face of the adjacent element which shares that face). The Dompierre algorithm can be used in such a non-tetrahedral conformal mesh to subdivide all elements into tetrahedra. J. Dompierre et al, supra. While the Dompierre et al. strategy is very elegant and fast, and requires no Steiner points, it cannot be applied to subdivide initially non-conformal meshes. As Dompierre observes, the problem of subdividing meshes occurs, e.g., in computer graphics where certain meshes must be subdivided into tetrahedra to use efficient algorithms for volume rendering, iso-contouring and particle advection.
In “non-conformal” meshes, abutting triangular faces initially constrain the choice of diagonal for some quadrilateral faces, so that Dompierre cannot be used. These initial constraints can directly or indirectly result in “overconstrained” prisms or hexahedra, i.e., those that cannot be subdivided into tetrahedra without adding Steiner points. In an initial mesh having prisms, hexahedra and tetrahedra, to subdivide the mesh, determinations are needed for splitting each quadrilateral face with a diagonal. Not all possible diagonal choices, for each prism and hexahedra, have a corresponding tetrahedralization. Non-conformalities in an initial mesh constrain the subdivision of some prisms and hexahedra. In some cases, an element may initially be, or may become during subdivision, overconstrained, making a consistent subdivision impossible. In such a case, a Steiner point must be used to subdivide an overconstrained element. Steiner points are undesirable, because they increase the mesh size and reduce the local mesh quality. In FIG. 1, an example of a non-conformal mesh situation is shown, with two tetrahedra abutting a hexahedron's quadrilateral face.
In FIGS. 2A–L, quadrilateral face constraint patterns are shown. FIGS. 2A–D are four divisible cases without a three-diagonal vertex. FIGS. 2E–L are alternating bit pattern cases, with no matched diagonals, no prisms possible; two of the cases are divisible (FIGS. 2K–L), six cases are not (FIGS. 2E–3J). The two divisible cases (FIGS. 2K–L) give five tetrahedra.
For subdividing elements in a non-conformal mixed element mesh, generally, certain random and non-random subdivisions have been proposed. Random subdivision subdivides a randomly selected first element, and each subsequent selection of an element to be subdivided also has no particular geometric basis. For example, a list of elements may be randomly generated, and subdivided in that random order.
Certain non-random approaches have been proposed, that take into account some geometrical feature, e.g., the strategy of Albertelli, et al. for subdividing an initially non-conformal mixed element mesh, i.e., to begin with subdividing the elements in random order, and use a “depth-first-search” subdivision approach. Albertelli's methodology may be imagined as starting randomly with any element, and then moving to an adjacent neighboring element for the next subdivision, each time moving to a neighboring element. While the Albertelli algorithm can subdivide these non-conformal meshes, the resulting subdivided mesh contains an undesirably large number of Steiner points.
Steiner points in tetrahedral mesh input cause interference and slow simulation time (such as by increasing node and element count; and introducing abrupt 2:1 mesh scale changes which degrade convergence). Minimizing added nodes (Steiner points) in tetrahedralizing meshes is important for making those meshes more useable by software applications requiring tetrahedral mesh input.